package 剑指Offer专项突破;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

public class Al75排序 {
    public static void main(String[] args) {
//        int[] arr = relativeSortArray(new int[]{28,6,22,8,44,17}, new int[]{22,28,8,6});
//        for (int i = 0; i < arr.length; i++) {
//            System.out.print(arr[i]+",");
//        }

        System.out.println(findKthLargest(new int[]{3,2,3,1,2,4,5,5,6}, 4));
    }

    /**
     * 数组相对顺序
     * 计数排序，  数组最大最小值范围不超过某个范围
     * @param arr1
     * @param arr2
     * @return
     */
    public static int[] relativeSortArray(int[] arr1, int[] arr2) {
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < arr1.length; i++) {
            min = Math.min(arr1[i], min);
            max = Math.max(arr1[i], max);
        }
        int[] count = new int[max-min+1];
        for (int i = 0; i < arr1.length; i++) {
            count[arr1[i]-min]++;
        }
        int index = 0;
        int[] result = new int[arr1.length];
        while (index<arr1.length) {
            for (int num : arr2) {
                while (count[num-min]-- >0) {
                    result[index++] = num;
                }
            }
            for (int i = 0; i < count.length; i++) {
                    while (count[i]-- >0) {
                        result[index++] = min + i;
                    }
                }
        }
        return result;
    }

    /**
     * 数组中第K大的元素
     * 1. 小顶堆
     * 2. 快速排序，分区
     * @param nums
     * @param k
     * @return
     */
    public static int findKthLargest(int[] nums, int k) {

        Queue<Integer> queue = new PriorityQueue<>(Comparator.comparingInt(t -> t));

        for (int i = 0; i < nums.length; i++) {
            if(queue.size()<k) {
                queue.offer(nums[i]);
            }else if(queue.peek()<nums[i]) {
                queue.poll();
                queue.offer(nums[i]);
            }
        }
        return queue.peek();
    }
}
